package demo1;

import java.util.ArrayList;
import java.util.List;

public class LeetCode438 {
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] arrs = s.toCharArray();
        char[] arrp = p.toCharArray();
        int ns = arrs.length, np = arrp.length;
        int[] hash1 = new int[200];
        int[] hash2 = new int[200];
        for(int i = 0; i < np; i++)
            hash1[arrp[i]]++;
        for(int left = 0, right = 0; right < ns; right++) {
            int len = right - left + 1;
            int in = arrs[right];
            hash2[in]++;
            if(len > np) {
                int out = arrs[left];
                hash2[out]--;
                left++;
            }
            boolean flag = cheak(hash1, hash2);
            if(flag) list.add(left);
        }
        return list;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] arrs = s.toCharArray();
        char[] arrp = p.toCharArray();
        int ns = arrs.length, np = arrp.length;
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(int i = 0; i < np; i++)
            hash1[arrp[i] - 'a']++;
        for(int left = 0, right = 0; right < ns; right++) {
            int len = right - left + 1;
            char in = arrs[right];
            hash2[in - 'a']++;
            if(len > np) {
                char out = arrs[left];
                hash2[out - 'a']--;
                left++;
            }
            boolean flag = cheak(hash1, hash2);
            if(flag) list.add(left);
        }
        return list;
    }
    private boolean cheak(int[] arr1, int[] arr2) {
        for(int i = 0; i < arr1.length; i++)
            if(arr1[i] != arr2[i])
                return false;
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] arrs = s.toCharArray();
        char[] arrp = p.toCharArray();
        int ns = arrs.length, np = arrp.length;
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(int i = 0; i < np; i++)
            hash1[arrp[i] - 'a']++;
        for(int left = 0, right = 0, count = 0; right < ns; right++) {
            int len = right - left + 1;
            char in = arrs[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if(len > np) {
                char out = arrs[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            if(count == np) list.add(left);
        }
        return list;
    }
}
